/*
 *https://leetcode.cn/problems/count-complete-tree-nodes/
 *222. 完全二叉树的节点个数
 *easy 吴朝泽 2024.9.13
 *递归 / 二分查找
递归法就是简单遍历，不为根就继续跑
二分查找法利用了完全二叉树的一个性质，可以判断左右子树的深度是否相同？
如果相同的话，说明左子树一定是满二叉树，节点数为 2 ^ left - 1 ，加上 root 就是 2 ^ left，
节点总数为左子树的节点加上递归调用右子树的节点；
如果不相同，说明右子树一定是满二叉树，同理可得节点数为 2 ^ right，
节点总数为右子树的节点加上递归调用左子树的节点。
*/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

//递归法 效率低 时间复杂度为 O(n)
class Solution {
public:
    int countNodes(TreeNode* root) {
        if (!root) 
            return 0;
        else
            return 1 + countNodes(root->left) + countNodes(root->right);
    }
};

//二分查找
class Solution {
public:
    int depth(TreeNode* root) 
    {
        int d;
        for (d = 0; root; root = root->left)   ++d;
        return d;
    }

    int countNodes(TreeNode* root) {
        if (!root)  return 0;
        int left = depth(root->left);
        int right = depth(root->right);
        if (left == right) 
            return (1 << left) + countNodes(root->right);
        else
            return (1 << right) + countNodes(root->left);
    }
};